
//
// Borrowed from the C example of the Shunting Yard algorithm on wiki
// http://en.wikipedia.org/wiki/Shunting-yard_algorithm
//

#ifndef INFIX_TO_RPN_H
#define INFIX_TO_RPN_H

#include <string>
#include <iostream>
#include <stack>

// operators
// precedence   operators       associativity
// 1			.				left to right
// 2            * /             left to right
// 3            + -             left to right
// 4            = < >           right to left
// 5			not				right to left
// 6			and 			left to right
// 7			or				left to right
int op_preced(const std::string& op)
{
	if(op.length() == 1)
	{
		switch(op[0])
		{
			case '.':
				return 7;
			case '*': case '/':
				return 6;
			case '+': case '-':
				return 5;
			case '=': case '<': case '>':
				return 4;
			default:
				std::cout << "Invalid op for preced check: " << op << std::endl;
		}
	}
	else
	{
		if(op.compare("not") == 0)
			return 3;
		else if(op.compare("and") == 0)
			return 2;
		else if(op.compare("or") == 0)
			return 1;
	}
	std::cout << "Operator not recognized while converting to RPN: " << op << std::endl;
	return 0;
}

bool op_left_assoc(const std::string& op)
{
	if(op.length() == 1)
	{
		switch(op[0])
		{
			// left to right
			case '.': case '*': case '/': case '+': case '-':
				return true;

			// right to left
			case '=': case '<': case '>':
				return false;
    	}

	}
	else
	{
		if(op.compare("not") == 0)
			return false;
		else if((op.compare("and") == 0) || (op.compare("or") == 0))
			return true;

	}
	std::cout << "Operator not recognized while converting to RPN: " << op << std::endl;
    return false;
}
 
unsigned int op_arg_count(const std::string& op)
{
	if(op.length() == 1)
	{
		if((op[0] == '.') || (op[0] == '*') || (op[0] == '/') || (op[0] == '+') 
			|| (op[0] == '-') || (op[0] == '=') || (op[0] == '<') || (op[0] == '>'))
			return 2;
	}
	else
	{
		if(op.compare("not") == 0)
			return 1;
		else if((op.compare("and") == 0) || (op.compare("or") == 0))
			return 2;

	}
	std::cout << "Operator not recognized while converting to RPN: " << op << std::endl;
    return 0;
}

bool is_operator(const std::string& op)
{
	if(op.length() == 1)
	{
		if((op[0] == '.') || (op[0] == '*') || (op[0] == '/') || (op[0] == '+') 
			|| (op[0] == '-') || (op[0] == '=') || (op[0] == '<') || (op[0] == '>'))
			return true;
	}
	else if((op.compare("not") == 0) || (op.compare("and") == 0) || (op.compare("or") == 0))
	{
		return true;
	}
    return false;
}

bool shunting_yard(const std::vector<std::string>& infix, std::vector<std::string>& rpn)
{
	unsigned int infixPtr = 0, infixEnd = infix.size();
	std::stack<std::string> operatorStack;
	std::string tempStr;

	while(infixPtr != infixEnd)
	{
		if(is_operator(infix[infixPtr]))
		{
			while(operatorStack.size() > 0)
			{
				tempStr = operatorStack.top();
				if(is_operator(tempStr) &&
					((op_left_assoc(infix[infixPtr]) && (op_preced(infix[infixPtr]) <= op_preced(tempStr))) ||
					(!op_left_assoc(infix[infixPtr]) && (op_preced(infix[infixPtr]) < op_preced(tempStr)))))
				{
					// pop the top off the stack onto the output queue
					rpn.push_back(tempStr);
					operatorStack.pop();
				}
				else
				{
					break;
				}
			}
			operatorStack.push(infix[infixPtr]);
		}
		else if(infix[infixPtr].compare("(") == 0)
		{
			// push opening parenthesis to stack
			operatorStack.push(infix[infixPtr]);
		}
		else if(infix[infixPtr].compare(")") == 0)
		{
			bool found = false;
			// Until the token at the top of the stack is a left parenthesis,
			// pop operators off the stack onto the output queue
			while(operatorStack.size() > 0)
			{
				tempStr = operatorStack.top();
				operatorStack.pop();
				if(tempStr.compare("(") == 0)
				{
					// don't add the left parenthesis to output
					found = true;
					break;
				}
				else
				{
					rpn.push_back(tempStr);
				}
			}
			// If the stack runs out without finding a left parenthesis, 
			// then there are mismatched parentheses.
			if(found == false)  
			{
				std::cout << "Error: parentheses mismatched\n";
				return false;
			}
		}
		else if(infix[infixPtr].compare("[") == 0)
		{
			// push opening parenthesis to stack
			operatorStack.push(infix[infixPtr]);
		}
		else if(infix[infixPtr].compare("]") == 0)
		{
			bool found = false;
			// Until the token at the top of the stack is a left parenthesis,
			// pop operators off the stack onto the output queue
			while(operatorStack.size() > 0)
			{
				tempStr = operatorStack.top();
				operatorStack.pop();
				if(tempStr.compare("[") == 0)
				{
					// don't add the left parenthesis to output
					found = true;
					break;
				}
				else
				{
					rpn.push_back(tempStr);
				}
			}
			// If the stack runs out without finding a left parenthesis, 
			// then there are mismatched parentheses.
			if(found == false)  
			{
				std::cout << "Error: parentheses mismatched\n";
				return false;
			}
		}
		else
		{
			// some variable or constant, add to output
			rpn.push_back(infix[infixPtr]);
		}
		++infixPtr;
	}
    // When there are no more tokens to read:
    // While there are still operator tokens in the stack:
	while(!operatorStack.empty())
	{
		tempStr = operatorStack.top();
		operatorStack.pop();
		if((tempStr.compare("(") == 0) || (tempStr.compare(")") == 0) ||
			(tempStr.compare("[") == 0) || (tempStr.compare("]") == 0))
		{
			std::cout << "Error: parentheses mismatched\n";
			return false;
		}
		rpn.push_back(tempStr);
	}
	return true;
}

#endif // INFIX_TO_RPN_H
